import random


class MySort():
    def __init__(self, arr_len):
        self.arr = []
        self.arr_len = arr_len  # 排序的长度
        self.teem_arr = [0]*self.arr_len
        self.boundary = 100


    def random_int(self):  # 随机数生成
        for i in range(self.arr_len):
            self.arr.append(random.randint(1, self.boundary-1))

    def bubble(self):  # 冒泡排序
        i = self.arr_len - 1
        arr = self.arr
        while i > 0:
            j = 0
            flag = 1
            while j < i:
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    flag = 0
                j += 1
            if flag:  # 如果某一趟没有交换过就代表有序
                break
            i -= 1

    def test_sort(self, sort_method, *args, **kwargs):
        print(self.arr)
        sort_method(*args, **kwargs)
        print(self.arr)

    def select(self):  # 选择排序
        for i in range(self.arr_len - 1):
            min_pos = i

            for j in range(i + 1, self.arr_len):
                if self.arr[j] < self.arr[min_pos]:
                    min_pos = j

            self.arr[i], self.arr[min_pos] = self.arr[min_pos], self.arr[i]

    def insert_sort(self):
        arr = self.arr
        i = 1
        while i < self.arr_len:
            insert_val = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > insert_val:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = insert_val
            i += 1

    def shell_sort(self):
        arr = self.arr
        gap = self.arr_len >> 1
        while gap > 0:
            i = gap
            while i < self.arr_len:
                insert_val = arr[i]
                j = i - gap
                while j >= 0 and arr[j] > insert_val:
                    arr[j + gap] = arr[j]
                    j -= gap
                arr[j + gap] = insert_val
                i += 1
            gap >>= 1

    def partition(self, left, right):
        arr = self.arr
        i = left
        k = left
        while i < right:
            if arr[i] < arr[right]:
                arr[k], arr[i] = arr[i], arr[k]
                k += 1
            i += 1
        arr[k], arr[right] = arr[right],arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def  ajust_max_hadp(self,dad,arr_len):
        """
        调整为大根堆或小根堆
        :param dad: 父亲节点
        :param arr_len: 数组长度
        :return:
        """
        arr = self.arr
        son = dad*2+1
        while son < arr_len:
            if son+1<arr_len and arr[son+1]<arr[son]:    #改变<或>可更改大根堆
                son = son+1
            if arr[son]<arr[dad]:                       #改变<或>可更改大根堆
                arr[son], arr[dad] = arr[dad],arr[son]
                dad = son
                son = dad*2+1
            else:
                break

    def heap_sort(self):
        arr = self.arr

        for i in range(self.arr_len//2-1,-1,-1):
            self.ajust_max_hadp(i,self.arr_len)
        arr[0], arr[-1] = arr[-1], arr[0]
        for i in range(self.arr_len-1,1,-1):
            self.ajust_max_hadp(0,i)
            arr[0], arr[i-1] = arr[i-1], arr[0]

    def merge(self,low,mid,high):
        arr = self.arr
        teem = self.teem_arr
        teem[low:high+1] =arr[low:high+1]
        i = low
        j = mid+1
        k = low
        while i<=mid and j<=high:
            if teem[i]<teem[j]:
                arr[k] = teem[i]
                k+=1
                i+=1
            else:
                arr[k] = teem[j]
                j+=1
                k+=1
        while i<=mid:
            arr[k] = teem[i]
            k+=1
            i+=1
        while j<=high:
            arr[k] = teem[j]
            j += 1
            k += 1



    def merge_sort(self,low,high):
        if low<high:
            mid = (low+high)//2
            self.merge_sort(low,mid)
            self.merge_sort(mid+1,high)
            self.merge(low,mid,high)

    def count_sort(self):
        cos = [0]*self.boundary
        arr = self.arr
        k = 0
        for i in range(self.arr_len):
            cos[arr[i]]+=1

        #回填到原数组arr
        for i in range(self.boundary):
            j = 0
            while j <cos[i]:    #i记录的是数值为几，cos[i]是数值为i的数有多少个
                arr[k] = i
                k+=1
                j+=1



if __name__ == '__main__':
    bubbles = MySort(10)
    bubbles.random_int()

    bubbles.test_sort(bubbles.count_sort)
